package com.llb666.java.leetcode.tree;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 给定一个二叉树，找出最小深度
 * 最小深度是从根节点到最近叶子节点的最短距离的节点数量
 * 深度优先，广度优先
 * Created by 斌~
 * 2021/4/29 16:32
 *                         1
 *                  2            3
 *             4       5       6
 *                           7
 */
public class 二叉树的最小深度 {
    public static void main(String[] args) {
        TreeNode treeNode7 = new TreeNode(7, null, null);
        TreeNode treeNode6 = new TreeNode(6, treeNode7, null);
        TreeNode treeNode5 = new TreeNode(5, null, null);
        TreeNode treeNode4 = new TreeNode(4, null, null);
        TreeNode treeNode3 = new TreeNode(3, treeNode6, null);
        TreeNode treeNode2 = new TreeNode(2, treeNode4, treeNode5);
        TreeNode treeNode1 = new TreeNode(1, treeNode2, treeNode3);

        System.out.println(minDepth(treeNode1));
        System.out.println(minDepth2(treeNode1));
    }

    /**
     * 深度优先
     */
    private static int minDepth(TreeNode root){
        if(root ==null){
            return 0;
        }
        if (root.left==null && root.right==null){
            return 1;
        }
        int min = Integer.MAX_VALUE;
        if (root.left!=null){
            min = Math.min(minDepth(root.left),min);
        }
        if (root.right!=null){
            min = Math.min(minDepth(root.right),min);
        }
        return min+1;
    }

    /**
     * 广度优先----从根节点查找到叶子节点就结束
     */
    private static int minDepth2(TreeNode root){
        if(root ==null){
            return 0;
        }
        Queue<TreeNode> queue =new LinkedList<>();
        root.deep = 1;
        queue.offer(root);
        while (!queue.isEmpty()){
            TreeNode node = queue.poll();
            if(node.right == null && node.left == null){
                return node.deep;
            }
            if(node.left != null){
                node.left.deep = node.deep+1;
                queue.offer(node.left);
            }
            if(node.right != null){
                node.right.deep = node.deep+1;
                queue.offer(node.right);
            }
        }
        return 0;
    }

    static class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        int deep;
        private TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

}
